package main

import (
	"fmt"
	"go_data_structures_and_algorithms/tool"
	"math"
)

func main() {
	//_, ints := tool.LenRandomValueRandom(10, 10)
	//fmt.Println(ints)
	arr := []int{8, 3, 4, 10, 5, 10, 6}

	fmt.Println(arr)
	MergeSort(arr)
	fmt.Println(arr)
}

/*
非递归的实现有点复杂
第一步得先定义一个步长和数组的长度N
归并排序本质上是一组一组地有序再形成全部有序
最小的一组就是步长就是1
两个步长为1的元素为一组
然后计算出这一组的L位置MID位置和R位置
在进行排序的操作的之前还需要计算好下一组是否能凑成完整的一组
通过Math.Min判断出N-1的长度长还是Mid加步长之后的长度长如果不加以判断MID+mergeSize的很可能会超出数组的长度
再通过merge函数传入三个参数进行排序
再将这组R的位置加1让L指向下一组的开头
*/

func MergeSort(arr1 []int) {
	if arr1 == nil && len(arr1) < 2 {
		return
	}
	N := len(arr1) // 边界条件
	// 1. 定义步长，即每次merge要合并的左右区间长度，mid-left+1
	mergeSize := 1
	L := 0

	for true {
		L = 0       //让L=0重置循环条件件
		for L < N { //如果L>N就终止条件否则会越界
			Mid := L + mergeSize - 1
			if Mid >= N { //可能会出现L<N但是加上mergeSize的话就会超出N的这时就该弹出要不然会越界
				break
			}
			R := int(math.Min(float64(N-1), float64(Mid+mergeSize))) //这里就是判断已经凑好一组的情况下
			fmt.Println(L, Mid, R)
			// 下一组可能遇到缺斤少两的情况这时候就要判断数组的长度和下一组组成的长度哪个更短就选哪个
			tool.Merge(arr1, L, Mid, R) //将数组和三个坐标传入将两组数据排成有序数组
			L = R + 1                   //L跳到下一组的开头

		}
		if mergeSize > N/2 {
			break // 等于N/2时，还要处理，再扩大两倍，总的区间长度一定不小于N,所有数一定处理完了
		}
		mergeSize <<= 1 //一个一组的排序完后就该让mergeSizex2开始两个一组的排序

	}

}
